The field of the invention is the reproduction of continuous tone images in the graphic arts electronic prepress environment. Continuous tone images, hereinafter referred to as "contone images", represent photographs and artwork as well as tints and degrades, and are characterized by image tones which can take on a continuous range of values. Contone images are typically stored in digital processing systems as one or more 8-bit bytes for each resolution element (i.e., each pixel) of the original image, with a single byte per pixel used to represent a monochrome image, and two or more bytes per pixel if color information is retained.
Reproduction of contone images in an output medium provides special problems in that many reproduction methods are capable of producing only a small number of image tones. In the case of offset printing, for example, there are only two stable tones, corresponding to the presence or absence of ink at any point on the output medium. In order to produce the visual effect of variable densities, the actual contone data values representing an image are converted into a spatial distribution of binary dots that can be printed, a process known in the art as "halftoning", or "halftone screening".
In a typical halftoning procedure, a contone image is rendered by comparing the contone data value at each individual resolution element of the recorder device to a reference value with the result being "black" if greater than the reference value and "white" otherwise. As used herein, the terms "black" and "white" refer to the presence or absence of ink on the printed output respectively. The reference values are spatially distributed within a repeating array referred to as a "threshold value array", or as a "threshold screen tile", according to a pattern determined by the halftone screening technique being used (e.g., "dot-size modulation" screening or "dot-frequency modulation" screening).
For high-quality graphic output, the reproduction device is typically a digital film recorder employing a scanning laser beam that exposes a photosensitive material at high resolution, usually 1200 dots per inch (dpi) or higher. The resolution of a contone image to be output is typically in the vicinity of 400 dpi (e.g., the input scanning resolution of a photograph). The halftoning process becomes one of projecting a spatial density distribution at a relatively low frequency (the contone image) upon another at the higher output spatial frequency distribution (the threshold values). In the above example, three output resolution elements are processed for each contone image pixel. This process is referred to as "image scaling", and typically takes place within the halftone screening subsystem of a raster image processor ("RIP").
Due to the demand for ever higher quality output and higher rates of production (system throughput) within the graphic arts electronic prepress environment, the processing performance demands of a halftone screening subsystem continue to increase. The throughput limitations placed by the image scaling process determine, to a large extent, the overall performance of an image reproduction system. This is due to the fact that the threshold comparison process must be carried out once for each resolution element of the output device. Doubling the resolution of the output device therefore has the effect of quadrupling the number of thresholding operations required for a given output image size. Acceleration techniques which minimize the processing time per output resolution element, including the image scaling processing time, have a direct impact on the utility of a halftoning system, and have been the subject of considerable investigation in the art.
A primary method for image scaling used in halftone screening is incremental interpolation, whereby dimensional units having a given frequency are interpolated to units of the same dimension having a higher frequency by incremental accumulation of the higher frequency (smaller dimensional) units, until the running sum of the accumulated units exceeds a fixed reference value (hereinafter called the "transition value") marking transition to the next dimensional unit of the lower frequency. In the application of incremental interpolation to image scaling, a running sum is maintained in an internal register, referred to as an "accumulation sum", to which a fixed "accumulation constant" is added for each processing cycle (corresponding to one output resolution element). When the accumulation sum reaches the transition value, a "transition event" is signaled, and the accumulation sum is reset by subtracting the transition value. For image scaling, the fixed constant represents the spatial dimension of an output resolution element, and the transition event indicates transition to another pixel of the contone image. Typically, an integer adder of N bits is used, configured such that the transition corresponds to 2.sup.N, implying a fixed binary point to the left of the most significant bit, with the fixed constant normalized accordingly. In this configuration therefore, the "transition event" is the output carry bit indicating overflow of the most significant bit of the adder.
The method described above, hereinafter referred to as "single incremental interpolation", has the advantage of maintaining the correct relative positioning between the high and low resolution domains, including provision for an initial phase shift (determined by the starting value of the accumulation sum), minimum interference effects between the low and high spatial frequencies (as compared for example to schemes dependent upon subdivision of a fundamental frequency), and for relative simplicity of implementation. It has the disadvantage of lengthening the hardware processing cycle and is therefore potentially slow.
The factor limiting the performance of the incremental interpolation method is the delays within each accumulation sum due to such effects as internal carry propagation. Methods aimed at minimizing this delay in adders and accumulators are well known in the art, and include such techniques such as carry-look-ahead, carry-save, and carry-select. One such method, referred to herein as "pipelined serial interpolation", eliminates internal carry propagation, giving a speed enhancement of a factor of N for an N-bit word. Speed enhancements over and above those described above require parallel processing of more than one output resolution element at the same time, and are heretofore unknown in the art.
It is therefore a general object of the invention to provide enhanced data processing throughput in a raster image processor.
It is a specific object of the invention to provide enhanced data processing throughput in a raster image processor by maximizing the speed of incremental interpolation used in image scaling.
It is a still further specific object of the invention to provide parallel processing of more than a single output resolution element within a single unit of processing time.